import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2023-03-13
 * Time: 13:01
 */
public class Day21 {
    //3.无重复字符的最长子串 - 6
    public static int lengthOfLongestSubstring1(String s) {
        char[] c = s.toCharArray();

        if (c.length == 0) {
            return 0;
        }
        int i = 0, k = 0, j = 1;
        int ret = 1, count = 1;
        while (j < c.length) {
            int l = ret + i;
            for (k = i; k < l; k++) {
                if (c[k] == c[j]) {
                    i++;
                    ret = 1;
                    break;
                }
            }
            if (k == l) {
                j++;
                ret++;
            } else {
                j = i + 1;
            }
            if (ret > count) {
                count = ret;
            }
            if (c.length - j + 1 <= count) {
                return count;
            }
        }
        return count;
    }

    //滑动窗口
    public int lengthOfLongestSubstring(String s) {
        int[] last = new int[128];
        for (int i = 0; i < 128; i++) {
            last[i] = -1;
        }
        int n = s.length();

        int res = 0;
        int start = 0;
        char[] c = s.toCharArray();
        for (int i = 0; i < n; i++) {
            int index = c[i];
            start = Math.max(start, last[index] + 1);
            res = Math.max(res, i - start + 1);
            last[index] = i;
        }

        return res;
    }

    //5.最长回文子串 -- 标记
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }

        int[] range = new int[2];
        char[] c = s.toCharArray();
        for (int i = 0; i < c.length; i++) {
            i = findLongest(c, i, range);
        }
        return s.substring(range[0], range[1] + 1);
    }

    public static int findLongest(char[] str, int low, int[] range) {
        int high = low;
        while (high < str.length - 1 && str[low] == str[high + 1]) {
            high++;
        }
        int ans = high;
        while (low > 0 && high < str.length - 1 && str[low - 1] == str[high + 1]) {
            low--;
            high++;
        }
        if (high - low > range[1] - range[0]) {
            range[0] = low;
            range[1] = high;
        }
        return ans;
    }

    //6.N字形变换
    public String convert(String s, int numRows) {
        if (numRows < 2) {
            return s;
        }

        StringBuilder[] sb = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            sb[i] = new StringBuilder();
        }
        int i = 0, flag = -1;
        for (char c : s.toCharArray()) {
            sb[i].append(c);
            if (i == 0 || i == numRows - 1) {
                flag = -flag;
            }
            i += flag;
        }
        StringBuilder ret = new StringBuilder();
        for (StringBuilder b : sb) {
            ret.append(b);
        }
        return ret.toString();
    }

    //7.整数反转
    public int reverse(int x) {
        int result = 0;
        while (x != 0) {
            int digit = x % 10;
            if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && digit > 7)) {
                return 0;
            }
            if (result < Integer.MIN_VALUE / 10 || (result == Integer.MIN_VALUE / 10 && digit < -8)) {
                return 0;
            }
            result = result * 10 + digit;
            x /= 10;
        }
        return result;
    }

    //8.字符串转换整数
    public int myAtoi1(String s) {
        char[] c = s.toCharArray();

        StringBuilder sbb = new StringBuilder();
        Character mc = ' ';
        for (int i = 0; i < c.length; i++) {
            if (mc == ' ' && sbb.length() == 0 && c[i] == ' ') {
                continue;
            } else if (sbb.length() == 0 && mc == ' ' && c[i] == '-') {
                mc = '-';
            } else if (sbb.length() == 0 && mc == ' ' && c[i] == '+') {
                mc = '+';
            } else if (c[i] >= '0' && c[i] <= '9') {
                sbb.append(c[i]);
            } else {
                break;
            }
        }
        int j = 0;
        for (char rc:sbb.toString().toCharArray()){
            if (rc == '0'){
                j++;
            }else{
                break;
            }
        }
        String sb = sbb.substring(j, sbb.length());
        if (sb.length() == 0) {
            return 0;
        }
        if (sb.length() > 10){
            if (mc == '-'){
                return Integer.MIN_VALUE;
            }else{
                return Integer.MAX_VALUE;
            }
        }else{
            long l = Long.valueOf(sb);
            if (mc == '-') {
                l = -l;
            }
            if ((int)l == l){
                return (int)l;
            }else if (mc == '-'){
                return Integer.MIN_VALUE;
            }else{
                return Integer.MAX_VALUE;
            }
        }
    }
    //优解
    public int myAtoi(String str) {
        char[] chars = str.toCharArray();
        int n = chars.length;
        int idx = 0;
        while (idx < n && chars[idx] == ' ') {
            // 去掉前导空格
            idx++;
        }
        if (idx == n) {
            //去掉前导空格以后到了末尾了
            return 0;
        }
        boolean negative = false;
        if (chars[idx] == '-') {
            //遇到负号
            negative = true;
            idx++;
        } else if (chars[idx] == '+') {
            // 遇到正号
            idx++;
        } else if (!Character.isDigit(chars[idx])) {
            // 其他符号
            return 0;
        }
        int ans = 0;
        while (idx < n && Character.isDigit(chars[idx])) {
            int digit = chars[idx] - '0';
            if (ans > (Integer.MAX_VALUE - digit) / 10) {
                // 本来应该是 ans * 10 + digit > Integer.MAX_VALUE
                // 但是 *10 和 + digit 都有可能越界，所有都移动到右边去就可以了。
                return negative? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
            ans = ans * 10 + digit;
            idx++;
        }
        return negative? -ans : ans;
    }
    //9.回文数
    public static boolean isPalindrome1(int x) {
        if (x < 0){
            return false;
        }
        StringBuilder sb1 = new StringBuilder();
        sb1.append(Integer.toString(x));
        StringBuilder sb2 = new StringBuilder();
        sb2.append(Integer.toString(x));
        sb2.reverse();
        if (sb1.toString().equals(sb2.toString())){
            return true;
        }else{
            return false;
        }
    }
    public boolean isPalindrome(int x){
        if (x < 0 || (x % 10 == 0 && x != 0)){
            return false;
        }

        int ret = 0;
        while (x > ret){
            ret = ret * 10 + x % 10;
            x /= 10;
        }
        return x == ret || x == ret / 10;
    }
}